Міністерство освіти і науки України Вінницький національний технічний університет Факультет інфотмаційних технологій та комп’ної інженерії Кафедра комп’ютерних наук Лабораторна робота №1 З дисципліни «Теорія Алгоритмів» Тема: «Аналіз алгоритму сортування методом вставки»  Тема: Аналіз алгоритму сортування методом вставки. Мета: навчитись аналізувати алгоритми на прикладі алгоритму сортування методом вставки Хід роботи Дослідження методу сортування вставками. Сортування вставками – алгоритм сортування в якому елементи вхідної послідовності переглядаються по одному і кожен наступний елемент розміщується в підходяще місце серед раніше упорядкованих елементів. Сортування вставками - простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як: швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: -простота у реалізації; -ефективний (за звичай) на маленьких масивах; -ефективний при сортуванні масивів, дані в яких вже непогано відсортовані; Ідея методу сортування вставками досить проста. Цей метод часто використовують при сортуванні карток: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже обробили (тим самим залишаючи їх відсортованими), при цьому більший елемент і всі елементи що знаходяться після нього зсуваються на 1 позицію вправо. Схема алгоритму, псевдокод, приклад дослідження. 02.1 Схема алгоритму:  2.2 Псевдокод: for j = 2 to A, length key = A [ j ] i = j - 1 While i > 0 and A [ i ] > key A [ i + 1 ] = A [ i ] i = i – 1 A [ i + 1 ] = key 2.3 Приклад дослідження: Нехай дано одномірний масив з такими елементами: 5, 1, 3, 4, 2. То згідно схеми алгоритму, зазначеної вище сортування буде відбуватися так: Створення програми, що сортирує масив методом вставки: Random zap = new Random(); Console.WriteLine("введіть кількість елементів масиву:"); int a = Convert.ToInt32(Console.ReadLine()); int[] arr1 = new int[a]; Console.WriteLine("початковий масив:"); //-Створення масиву for (int i = 0; i < a; i++) { arr1[i] = zap.Next(1, 100); Console.Write(arr1[i] + " "); } //////////// Сортування масиву в порядку зростання //////////// Stopwatch watch = new Stopwatch(); // -Cтворення таймера; watch.Start(); // -Запуск таймера; for (int j = 1; j < arr1.Length; j++) // -Cтворюємо лічильник зі змінною j, яка дор. // ідентифікатору наступного елемента массива; { int key = arr1[j]; // -Вводимо змінну key яка буде перевіряти чи // більше попереднє число наступного; int i = j - 1; // -Вводимо змінну і, яка дор. ідентефікатору // попереднього елемента массива; while (i >= 0 && arr1[i] > key) // -Перевіряємо умову чи змінна і більша або // дор. 0 та чи попередній елемент массиву // більший за змінну key; { // arr1[i + 1] = arr1[i]; // -Елемент стає на своє місце в відсортованій i = i - 1; } // частині массиву; arr1[i + 1] = key; } watch.Stop(); // -Зупинка таймера; Console.WriteLine("\nВідсортований по зростанню масив:"); for (int i = 0; i < arr1.Length; i++) { Console.Write(arr1[i] +" "); } Console.WriteLine("\Час виконання програми в мілісекунд...